1. Field of the Invention
The present invention relates to the field networking and, more particularly, to the field of routers in networks.
2. Description of the Related Art
Networks provide for transmission of information from a source to a destination over a particular route. The information is transmitted along the route through routers. Typically, each router has knowledge of various routes available in the network and this knowledge is stored in a route database or route table. The information is transmitted in accordance with a particular protocol and routers in the network may support any of a number of protocols. Thus, the router may store multiple routes which are available using multiple protocols.
An example of a routing table is shown in FIG. 1 which illustrates a table 100 having a plurality of entries, one for each of routes R1 to R5, 101. Each entry includes a sequence number 103 and other information 102. The other information may include, for example, next hop information (i.e., identification of the next router in the route), various metrics which describe the route (e.g., number of hops, bandwidth), and route preference information.
The sequence number 103 is changed each time there is a change to the route. Further, each time any route in the table changes, a table sequence number 105 is updated. In this way, as will be seen, it can be easily determined whether any route in the table has changed since the last time the table was examined. If there has been a change, individual routes are examined to determine which routes changed.
It is desirable to exchange routes between the various protocols. This is typically done via the central routing table 100 using either a polling or interrupt mechanism. For example, using the polling method, periodically, the table is queried by each protocol to determine if there have been changes to the various routes from other protocols which are of interest (in the interrupt type mechanism, an interrupt occurs when routes are changed). Initially, the table sequence number 105 is checked to see if it has changed since the last time the table was polled. If it has not changed, no changes have been made to the routes of interest. If the table sequence number 105 has changed, then sequence numbers of the individual routes of interest are checked to determine if they have changed.
Unfortunately, if just one route has changed, even one that is not of interest, all routes must still be checked. This can, in a typical implementation having thousands (even hundreds of thousands) of routes, be computationally burdensome. The burden is increased because in a typical implementation, the polling process may be required to take place quite frequently (e.g., every several seconds).
Thus, it would be desirable to develop a system in which the overhead burden of determining which routes in routing table have changed is reduced.
A route table providing a list of pointers to checksum values computed across routes of interest to a particular protocol is described. When the protocol wishes to determine whether routes in the table have changed since the last time the table was examined, the checksum value may be examined to determine if it has changed since the last time the table was examined. If the checksum value has changed, individual routes of interest are examined to determine which route or routes of interest have changed.